package com.zxy.leetcode._00000_00099._00010_00019;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/3sum-closest/
 *
 * 最接近的三数之和
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 *
 * 3 <= nums.length <= 10^3
 * -10^3 <= nums[i] <= 10^3
 * -10^4 <= target <= 10^4
 *
 */
public class Test00016 {

    public static void main(String[] args) {
        System.out.println(Math.abs(Integer.MIN_VALUE));
        Test00016 test = new Test00016();
        int[] nums = {-3,-2,-5,3,-4};
        System.out.println(test.threeSumClosest(nums, -1));
    }

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);

        // Math.abs(Integer.MIN_VALUE) 得到是一个负值，只能根据题目要求设置一个比较接近的值
        int closest = 100_000;

        for (int i=0; i<=nums.length-3; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int l = i+1;
            int r = nums.length-1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == target) {
                    return target;
                }else if (sum > target) {
                    r --;
                }else {
                    l ++;
                }
                if (Math.abs(sum - target) < Math.abs(closest-target)) {
                    closest = sum;
                }
            }
        }

        return closest;
    }

}
